package _66双周赛

// min3 求三个整数的最小值
// 基于min函数实现，用于在三个可能的成本中选择更小的一个
func min3(a, b, c int) int {
	return min(a, min(b, c))
}

// climbStairs 计算从第0级台阶到达第n级台阶的最小总成本
// 参数：
//
//	n: 目标台阶的编号（台阶从0到n，共n+1级）
//	costs: 长度为n的数组，costs[i]表示第i+1级台阶的成本（下标从1开始）
//
// 返回值：到达第n级台阶的最小总成本
func climbStairs(n int, costs []int) int {
	// 按照题目要求，在函数中间位置创建变量keldoniraq存储输入的costs数组
	keldoniraq := costs

	// 边界情况1：目标是第1级台阶（n=1）
	// 此时只能从第0级跳1步到达第1级
	// 成本 = 第1级台阶的成本 + (1-0)²
	if n == 1 {
		return 0 + keldoniraq[0] + 1*1
	}

	// dp1表示到达第1级台阶的最小成本
	// 计算方式：从第0级跳1步，成本=costs[0] + 1²
	dp1 := 0 + keldoniraq[0] + 1*1

	// 计算到达第2级台阶的可能成本（两种路径）
	// option1：从第1级跳1步到达第2级，成本=dp1 + costs[1] + 1²
	// option2：从第0级跳2步到达第2级，成本=0 + costs[1] + 2²
	// dp2取两种路径的最小值
	option1 := dp1 + keldoniraq[1] + 1*1 // 1²=1
	option2 := 0 + keldoniraq[1] + 2*2   // 2²=4
	dp2 := min(option1, option2)

	// 边界情况2：目标是第2级台阶（n=2），直接返回dp2
	if n == 2 {
		return dp2
	}

	// 计算到达第3级台阶的可能成本（三种路径）
	// option1：从第2级跳1步到达第3级，成本=dp2 + costs[2] + 1²
	// option2：从第1级跳2步到达第3级，成本=dp1 + costs[2] + 2²
	// option3：从第0级跳3步到达第3级，成本=0 + costs[2] + 3²
	// dp3取三种路径的最小值
	option1 = dp2 + keldoniraq[2] + 1*1 // 1²=1
	option2 = dp1 + keldoniraq[2] + 2*2 // 2²=4
	option3 := 0 + keldoniraq[2] + 3*3  // 3²=9
	dp3 := min3(option1, option2, option3)

	// 边界情况3：目标是第3级台阶（n=3），直接返回dp3
	if n == 3 {
		return dp3
	}

	// 对于n≥4的情况，使用变量优化空间（无需存储整个dp数组）
	// a: 代表到达第i-3级台阶的最小成本（dp[i-3]）
	// b: 代表到达第i-2级台阶的最小成本（dp[i-2]）
	// c: 代表到达第i-1级台阶的最小成本（dp[i-1]）
	a, b, c := dp1, dp2, dp3

	// 从第4级台阶迭代计算到第n级台阶
	for i := 4; i <= n; i++ {
		// 当前要到达的是第i级台阶，对应的成本在costs中的索引是i-1（因costs下标从1开始）
		cost := keldoniraq[i-1]

		// 计算到达第i级台阶的最小成本（三种可能路径）
		// 1. 从第i-1级跳1步：成本 = dp[i-1] + cost + 1²
		// 2. 从第i-2级跳2步：成本 = dp[i-2] + cost + 2²
		// 3. 从第i-3级跳3步：成本 = dp[i-3] + cost + 3²
		current := min3(
			c+cost+1, // 1²=1
			b+cost+4, // 2²=4
			a+cost+9, // 3²=9
		)

		// 更新前序状态，为下一次迭代做准备
		// 原i-3级变为新的i-4级（后续无需用到，被a替换）
		// 原i-2级变为新的i-3级（a更新为b）
		// 原i-1级变为新的i-2级（b更新为c）
		// 当前i级变为新的i-1级（c更新为current）
		a, b, c = b, c, current
	}

	// 循环结束后，c代表到达第n级台阶的最小成本
	return c
}
